package primary.primary0;

public class S0041缺失的第一个正数 {
    /**
     * 98，看了答案思路
     * 注意两点
     * 1 结果一定是在 1 -> n + 1 之间的
     * 2 0是不算的，所以要交换的位置是nums[i] - 1
     */
    class Solution {
        public int firstMissingPositive(int[] nums) {
            for(int i = 0; i < nums.length; i++){
                // 把i位置的值一直往对应的地方去换，注意防止两数相同死循环，所以要做一个相等判断
                while(0 <= (nums[i] - 1) && (nums[i] - 1) < nums.length && nums[i] != nums[(nums[i] - 1)]){
                    swap(nums, i, (nums[i] - 1));
                }
            }
            // 换完了，第一个没出现的值就是第一个缺失的，如果没有的话，就是nums.length + 1
            int res = nums.length + 1;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] != i + 1){
                    res = i + 1;
                    break;
                }
            }
            return res;
        }
        private void swap(int[] nums, int locA, int locB){
            int temp = nums[locA];
            nums[locA] = nums[locB];
            nums[locB] = temp;
        }
    }
}
